package heap;

import java.util.Comparator;
import java.util.PriorityQueue;

class MedianofTwoSortedArray04 {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o2, o1);
            }
        });

        int m = nums1.length;
        int n = nums2.length;
        int minHeapSize = (m + n) >> 1, maxHeapSize = m + n - minHeapSize;

        for (int i = nums1.length - 1; i >= 0; i--) {
            if (minHeap.size() < minHeapSize)
                minHeap.add(nums1[i]);
            else
                maxHeap.add(nums1[i]);
        }


        for (int i = nums2.length - 1; i >= 0; i--) {
            if (minHeap.isEmpty() || minHeap.size() < minHeapSize) {
                minHeap.add(nums2[i]);
            } else if (nums2[i] > minHeap.peek()) {
                maxHeap.add(minHeap.poll());
                minHeap.add(nums2[i]);
            } else
                maxHeap.add(nums2[i]);
        }
        System.out.println();
        if (m + n == 1)
            return maxHeap.isEmpty() ? minHeap.poll() : maxHeap.poll();
        else if (m + n == 0)
            return 0;
        double median =
                (m + n) % 2 == 0 ?
                        (Double.valueOf(maxHeap.poll()) + Double.valueOf(minHeap.poll())) / 2
                        : maxHeap.poll();
        return median;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1};
        int[] nums2 = new int[]{};
        System.out.println(findMedianSortedArrays(nums1, nums2));
    }
}